package leetcode_900;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

/**
 *@author 周杨
 *KSimilarStrings_854 给定两个字符串 问最少交换A多少次数字母 能变成B
 *describe:用广度优先搜索 很好的题目 AC 20%
 *2018年11月4日 下午3:26:14
 */
public class KSimilarStrings_854_ {
	/**
	 * describe:企图使用贪心算法 把最近的字母调过来 但是这种思想错误
	 * 因为如同"bccaba" "abacbc" 会把第一个b调走
	 * 2018年11月4日 下午2:57:58
	 */
	public int kSimilarity1(String A, String B) {
        char[] strA=A.toCharArray();
        char[] strB=B.toCharArray();
        int res=0;
        for(int i=0;i<A.length();++i) {
        	if(strA[i]==strB[i]) continue;
        	int j=i+1;
        	while(j<A.length()) {
        		if(strA[j]==strB[i]&&strA[j]!=strB[j]) {
        			strA[j]=strA[i];
        			++res;
        		}
        		++j;
        	}
        }
        return res;
    }
	
	public int kSimilarity(String A, String B) {
		Queue<String> queue=new LinkedList<String>();
		queue.offer(A);
		
		Map<String,Integer> map=new HashMap<String,Integer>();
		map.put(A, 0);
		
		while(!queue.isEmpty()) {
			String s=queue.poll();
			if(s.equals(B)) return map.get(s);
			for(String now:help(s,B)) {
				if(!map.containsKey(now)) {
					map.put(now, map.get(s)+1);
					queue.offer(now);
				}
			}
		}
		return 0;
	}
	
	public List<String> help(String A,String B){
		List<String> res=new ArrayList<String>();
		int i=0;
		while(A.charAt(i)==B.charAt(i)) ++i;//因为最多只有20位 可以这样傻瓜搜索
		int j=i+1;
		while(j<A.length()) {
			if(A.charAt(j)==B.charAt(i)) {
				char[] chars=A.toCharArray();
				char temp=chars[i];
				chars[i]=chars[j];
				chars[j]=temp;
				res.add(new String(chars));
			}
			++j;
		}
		return res;
	}
}
